package com.leetcode.partition10;

/**
 * @author `RKC`
 * @date 2021/11/6 22:13
 */
public class LC912排序数组 {

    public static int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }

    private static void heapSort(int[] nums) {
        //从最后一个有孩子的节点开始，构建大顶堆
        for (int i = (nums.length - 2) / 2; i >= 0; i--) {
            adjustToMaximumHeap(nums, i, nums.length);
        }
        int size = nums.length;
        //将堆顶元素放到最后，继续调整大顶堆
        int temp = nums[0];
        nums[0] = nums[--size];
        nums[size] = temp;

        for (int i = 0; i < nums.length - 1; i++) {
            adjustToMaximumHeap(nums, 0, size);
            temp = nums[0];
            nums[0] = nums[--size];
            nums[size] = temp;
        }
    }

    private static void adjustToMaximumHeap(int[] nums, int i, int size) {
        //将数组有效长度size调整为一个大顶堆
        while (i <= size / 2) {
            int left = i * 2 + 1, right = i * 2 + 2;
            if ((left < size && nums[left] > nums[i]) || (right < size && nums[right] > nums[i])) {
                int childIndex = left;
                if (right < size && nums[right] > nums[left]) {
                    childIndex = right;
                }
                int temp = nums[childIndex];
                nums[childIndex] = nums[i];
                nums[i] = temp;
                i = childIndex;
            } else {
                break;
            }
        }
    }
}
